package net.sf.mxlosgi.mxlosgiutilsbundle.collections;

/**
 * $Revision: 1456 $ $Date: 2005-06-01 22:04:54 -0700 (Wed, 01 Jun 2005) $
 * 
 * Copyright 2003-2005 Jive Software.
 * 
 * All rights reserved. Licensed under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */

import java.util.*;

/**
 * A specialized Map that is size-limited (using an LRU algorithm) and has an
 * optional expiration time for cache items. The Map is thread-safe.
 * <p>
 * 
 * The algorithm for cache is as follows: a HashMap is maintained for fast
 * object lookup. Two linked lists are maintained: one keeps objects in the
 * order they are accessed from cache, the other keeps objects in the order they
 * were originally added to cache. When objects are added to cache, they are
 * first wrapped by a CacheObject which maintains the following pieces of
 * information:
 * <ul>
 * <li> A pointer to the node in the linked list that maintains accessed order
 * for the object. Keeping a reference to the node lets us avoid linear scans of
 * the linked list.
 * <li> A pointer to the node in the linked list that maintains the age of the
 * object in cache. Keeping a reference to the node lets us avoid linear scans
 * of the linked list.
 * </ul>
 * <p/> To get an object from cache, a hash lookup is performed to get a
 * reference to the CacheObject that wraps the real object we are looking for.
 * The object is subsequently moved to the front of the accessed linked list and
 * any necessary cache cleanups are performed. Cache deletion and expiration is
 * performed as needed.
 * 
 * @author Matt Tucker
 */
public class LifeTimeCache<K, V> implements Map<K, V>
{

	/**
	 * The map the keys and values are stored in.
	 */
	protected Map<K, CacheObject<V>> map;

	/**
	 * Linked list to maintain order that cache objects are accessed in,
	 * most used to least used.
	 */
	protected LinkedList lastAccessedList;

	/**
	 * Linked list to maintain time that cache objects were initially
	 * added to the cache, most recently added to oldest added.
	 */
	protected LinkedList ageList;

	/**
	 * Maximum number of items the cache will hold.
	 */
	protected int maxCacheSize;

	/**
	 * Maximum length of time objects can exist in cache before expiring.
	 */
	protected long maxLifetime;

	/**
	 * Maintain the number of cache hits and misses. A cache hit occurs
	 * every time the get method is called and the cache contains the
	 * requested object. A cache miss represents the opposite occurence.
	 * <p>
	 * 
	 * Keeping track of cache hits and misses lets one measure how
	 * efficient the cache is; the higher the percentage of hits, the more
	 * efficient.
	 */
	protected long cacheHits, cacheMisses = 0L;

	/**
	 * Create a new cache and specify the maximum size of for the cache in
	 * bytes, and the maximum lifetime of objects.
	 * 
	 * @param maxSize
	 *                  the maximum number of objects the cache will hold.
	 *                  -1 means the cache has no max size.
	 * @param maxLifetime
	 *                  the maximum amount of time (in ms) objects can
	 *                  exist in cache before being deleted. -1 means
	 *                  objects never expire.
	 */
	public LifeTimeCache(int maxSize, long maxLifetime)
	{
		if (maxSize == 0)
		{
			throw new IllegalArgumentException("Max cache size cannot be 0.");
		}
		this.maxCacheSize = maxSize;
		this.maxLifetime = maxLifetime;

		// Our primary data structure is a hash map. The default
		// capacity of 11
		// is too small in almost all cases, so we set it bigger.
		map = new HashMap<K, CacheObject<V>>(103);

		lastAccessedList = new LinkedList();
		ageList = new LinkedList();
	}

	public synchronized V put(K key, V value)
	{
		V oldValue = null;
		// Delete an old entry if it exists.
		if (map.containsKey(key))
		{
			oldValue = remove(key, true);
		}

		CacheObject<V> cacheObject = new CacheObject<V>(value);
		map.put(key, cacheObject);
		// Make an entry into the cache order list.
		// Store the cache order list entry so that we can get back
		// to it
		// during later lookups.
		cacheObject.lastAccessedListNode = lastAccessedList.addFirst(key);
		// Add the object to the age list
		LinkedListNode ageNode = ageList.addFirst(key);
		ageNode.timestamp = System.currentTimeMillis();
		cacheObject.ageListNode = ageNode;

		// If cache is too full, remove least used cache entries
		// until it is not too full.
		cullCache();

		return oldValue;
	}

	public synchronized V get(Object key)
	{
		// First, clear all entries that have been in cache longer
		// than the
		// maximum defined age.
		deleteExpiredEntries();

		CacheObject<V> cacheObject = map.get(key);
		if (cacheObject == null)
		{
			// The object didn't exist in cache, so increment
			// cache misses.
			cacheMisses++;
			return null;
		}
		// Remove the object from it's current place in the cache
		// order list,
		// and re-insert it at the front of the list.
		cacheObject.lastAccessedListNode.remove();
		lastAccessedList.addFirst(cacheObject.lastAccessedListNode);

		// The object exists in cache, so increment cache hits.
		// Also, increment
		// the object's read count.
		cacheHits++;
		cacheObject.readCount++;

		return cacheObject.object;
	}

	public synchronized V remove(Object key)
	{
		return remove(key, false);
	}

	/*
	 * Remove operation with a flag so we can tell coherence if the remove
	 * was caused by cache internal processing such as eviction or loading
	 */
	public synchronized V remove(Object key, boolean internal)
	{
		// noinspection SuspiciousMethodCalls
		CacheObject<V> cacheObject = map.remove(key);
		// If the object is not in cache, stop trying to remove it.
		if (cacheObject == null)
		{
			return null;
		}
		// Remove from the cache order list
		cacheObject.lastAccessedListNode.remove();
		cacheObject.ageListNode.remove();
		// Remove references to linked list nodes
		cacheObject.ageListNode = null;
		cacheObject.lastAccessedListNode = null;

		return cacheObject.object;
	}

	public synchronized void clear()
	{
		Object[] keys = map.keySet().toArray();
		for (Object key : keys)
		{
			remove(key);
		}

		// Now, reset all containers.
		map.clear();
		lastAccessedList.clear();
		ageList.clear();

		cacheHits = 0;
		cacheMisses = 0;
	}

	public synchronized int size()
	{
		// First, clear all entries that have been in cache longer
		// than the
		// maximum defined age.
		deleteExpiredEntries();

		return map.size();
	}

	public synchronized boolean isEmpty()
	{
		// First, clear all entries that have been in cache longer
		// than the
		// maximum defined age.
		deleteExpiredEntries();

		return map.isEmpty();
	}

	public synchronized Collection<V> values()
	{
		// First, clear all entries that have been in cache longer
		// than the
		// maximum defined age.
		deleteExpiredEntries();

		return Collections.unmodifiableCollection(new AbstractCollection<V>()
		{
			Collection<CacheObject<V>> values = map.values();

			public Iterator<V> iterator()
			{
				return new Iterator<V>()
				{
					Iterator<CacheObject<V>> it = values.iterator();

					public boolean hasNext()
					{
						return it.hasNext();
					}

					public V next()
					{
						return it.next().object;
					}

					public void remove()
					{
						it.remove();
					}
				};
			}

			public int size()
			{
				return values.size();
			}
		});
	}

	public synchronized boolean containsKey(Object key)
	{
		// First, clear all entries that have been in cache longer
		// than the
		// maximum defined age.
		deleteExpiredEntries();

		return map.containsKey(key);
	}

	@SuppressWarnings("unchecked")
	public void putAll(Map<? extends K, ? extends V> map)
	{
		for (Entry<? extends K, ? extends V> entry : map.entrySet())
		{
			V value = entry.getValue();
			// If the map is another DefaultCache instance
			// than the
			// entry values will be CacheObject instances that
			// need
			// to be converted to the normal object form.
			if (value instanceof CacheObject)
			{
				// noinspection unchecked
				value = ((CacheObject<V>) value).object;
			}
			put(entry.getKey(), value);
		}
	}

	@SuppressWarnings("unchecked")
	public synchronized boolean containsValue(Object value)
	{
		// First, clear all entries that have been in cache longer
		// than the
		// maximum defined age.
		deleteExpiredEntries();

		// noinspection unchecked
		CacheObject<V> cacheObject = new CacheObject<V>((V) value);

		return map.containsValue(cacheObject);
	}

	public synchronized Set<Map.Entry<K, V>> entrySet()
	{
		// Warning -- this method returns CacheObject instances and
		// not Objects
		// in the same form they were put into cache.

		// First, clear all entries that have been in cache longer
		// than the
		// maximum defined age.
		deleteExpiredEntries();

		return new AbstractSet<Map.Entry<K, V>>()
		{
			private final Set<Map.Entry<K, CacheObject<V>>> set = map.entrySet();

			public Iterator<Entry<K, V>> iterator()
			{
				return new Iterator<Entry<K, V>>()
				{
					private final Iterator<Entry<K, CacheObject<V>>> it = set.iterator();

					public boolean hasNext()
					{
						return it.hasNext();
					}

					public Entry<K, V> next()
					{
						Map.Entry<K, CacheObject<V>> entry = it.next();
						return new AbstractMapEntry<K, V>(entry.getKey(), entry.getValue().object)
						{
							@Override
							public V setValue(V value)
							{
								throw new UnsupportedOperationException("Cannot set");
							}
						};
					}

					public void remove()
					{
						it.remove();
					}
				};

			}

			public int size()
			{
				return set.size();
			}
		};
	}

	public synchronized Set<K> keySet()
	{
		// First, clear all entries that have been in cache longer
		// than the
		// maximum defined age.
		deleteExpiredEntries();

		return Collections.unmodifiableSet(map.keySet());
	}

	public long getCacheHits()
	{
		return cacheHits;
	}

	public long getCacheMisses()
	{
		return cacheMisses;
	}

	public int getMaxCacheSize()
	{
		return maxCacheSize;
	}

	public synchronized void setMaxCacheSize(int maxCacheSize)
	{
		this.maxCacheSize = maxCacheSize;
		// It's possible that the new max size is smaller than our
		// current cache
		// size. If so, we need to delete infrequently used items.
		cullCache();
	}

	public long getMaxLifetime()
	{
		return maxLifetime;
	}

	public void setMaxLifetime(long maxLifetime)
	{
		this.maxLifetime = maxLifetime;
	}

	/**
	 * Clears all entries out of cache where the entries are older than
	 * the maximum defined age.
	 */
	protected synchronized void deleteExpiredEntries()
	{
		// Check if expiration is turned on.
		if (maxLifetime <= 0)
		{
			return;
		}

		// Remove all old entries. To do this, we remove objects
		// from the end
		// of the linked list until they are no longer too old. We
		// get to avoid
		// any hash lookups or looking at any more objects than is
		// strictly
		// neccessary.
		LinkedListNode node = ageList.getLast();
		// If there are no entries in the age list, return.
		if (node == null)
		{
			return;
		}

		// Determine the expireTime, which is the moment in time
		// that elements
		// should expire from cache. Then, we can do an easy check
		// to see
		// if the expire time is greater than the expire time.
		long expireTime = System.currentTimeMillis() - maxLifetime;

		while (expireTime > node.timestamp)
		{
			if (remove(node.object, true) == null)
			{
				System.err.println("Error attempting to remove(" + node.object.toString()
						+ ") - cacheObject not found in cache!");
				// remove from the ageList
				node.remove();
			}

			// Get the next node.
			node = ageList.getLast();
			// If there are no more entries in the age list,
			// return.
			if (node == null)
			{
				return;
			}
		}
	}

	/**
	 * Removes the least recently used elements if the cache size is
	 * greater than or equal to the maximum allowed size until the cache
	 * is at least 10% empty.
	 */
	protected synchronized void cullCache()
	{
		// Check if a max cache size is defined.
		if (maxCacheSize < 0)
		{
			return;
		}

		// See if the cache is too big. If so, clean out cache until
		// it's 10% free.
		if (map.size() > maxCacheSize)
		{
			// First, delete any old entries to see how much
			// memory that frees.
			deleteExpiredEntries();
			// Next, delete the least recently used elements
			// until 10% of the cache
			// has been freed.
			int desiredSize = (int) (maxCacheSize * .90);
			for (int i = map.size(); i > desiredSize; i--)
			{
				// Get the key and invoke the remove
				// method on it.
				if (remove(lastAccessedList.getLast().object, true) == null)
				{
					System.err.println("Error attempting to cullCache with remove("
							+ lastAccessedList.getLast().object.toString() + ") - "
							+ "cacheObject not found in cache!");
					lastAccessedList.getLast().remove();
				}
			}
		}
	}

	/**
	 * Wrapper for all objects put into cache. It's primary purpose is to
	 * maintain references to the linked lists that maintain the creation
	 * time of the object and the ordering of the most used objects.
	 * 
	 * This class is optimized for speed rather than strictly correct
	 * encapsulation.
	 */
	private static class CacheObject<V>
	{

		/**
		 * Underlying object wrapped by the CacheObject.
		 */
		public V object;

		/**
		 * A reference to the node in the cache order list. We keep
		 * the reference here to avoid linear scans of the list.
		 * Every time the object is accessed, the node is removed
		 * from its current spot in the list and moved to the front.
		 */
		public LinkedListNode lastAccessedListNode;

		/**
		 * A reference to the node in the age order list. We keep
		 * the reference here to avoid linear scans of the list. The
		 * reference is used if the object has to be deleted from
		 * the list.
		 */
		public LinkedListNode ageListNode;

		/**
		 * A count of the number of times the object has been read
		 * from cache.
		 */
		public int readCount = 0;

		/**
		 * Creates a new cache object wrapper.
		 * 
		 * @param object
		 *                  the underlying Object to wrap.
		 */
		public CacheObject(V object)
		{
			this.object = object;
		}

		public boolean equals(Object o)
		{
			if (this == o)
			{
				return true;
			}
			if (!(o instanceof CacheObject))
			{
				return false;
			}

			final CacheObject<?> cacheObject = (CacheObject<?>) o;

			return object.equals(cacheObject.object);

		}

		public int hashCode()
		{
			return object.hashCode();
		}
	}

	/**
	 * Simple LinkedList implementation. The main feature is that list
	 * nodes are public, which allows very fast delete operations when one
	 * has a reference to the node that is to be deleted.
	 * <p>
	 */
	private static class LinkedList
	{

		/**
		 * The root of the list keeps a reference to both the first
		 * and last elements of the list.
		 */
		private LinkedListNode head = new LinkedListNode("head", null, null);

		/**
		 * Creates a new linked list.
		 */
		public LinkedList()
		{
			head.next = head.previous = head;
		}

		/**
		 * Returns the first linked list node in the list.
		 * 
		 * @return the first element of the list.
		 */
		public LinkedListNode getFirst()
		{
			LinkedListNode node = head.next;
			if (node == head)
			{
				return null;
			}
			return node;
		}

		/**
		 * Returns the last linked list node in the list.
		 * 
		 * @return the last element of the list.
		 */
		public LinkedListNode getLast()
		{
			LinkedListNode node = head.previous;
			if (node == head)
			{
				return null;
			}
			return node;
		}

		/**
		 * Adds a node to the beginning of the list.
		 * 
		 * @param node
		 *                  the node to add to the beginning of the
		 *                  list.
		 * @return the node
		 */
		public LinkedListNode addFirst(LinkedListNode node)
		{
			node.next = head.next;
			node.previous = head;
			node.previous.next = node;
			node.next.previous = node;
			return node;
		}

		/**
		 * Adds an object to the beginning of the list by
		 * automatically creating a a new node and adding it to the
		 * beginning of the list.
		 * 
		 * @param object
		 *                  the object to add to the beginning of
		 *                  the list.
		 * @return the node created to wrap the object.
		 */
		public LinkedListNode addFirst(Object object)
		{
			LinkedListNode node = new LinkedListNode(object, head.next, head);
			node.previous.next = node;
			node.next.previous = node;
			return node;
		}

		/**
		 * Adds an object to the end of the list by automatically
		 * creating a a new node and adding it to the end of the
		 * list.
		 * 
		 * @param object
		 *                  the object to add to the end of the
		 *                  list.
		 * @return the node created to wrap the object.
		 */
		public LinkedListNode addLast(Object object)
		{
			LinkedListNode node = new LinkedListNode(object, head, head.previous);
			node.previous.next = node;
			node.next.previous = node;
			return node;
		}

		/**
		 * Erases all elements in the list and re-initializes it.
		 */
		public void clear()
		{
			// Remove all references in the list.
			LinkedListNode node = getLast();
			while (node != null)
			{
				node.remove();
				node = getLast();
			}

			// Re-initialize.
			head.next = head.previous = head;
		}

		/**
		 * Returns a String representation of the linked list with a
		 * comma delimited list of all the elements in the list.
		 * 
		 * @return a String representation of the LinkedList.
		 */
		public String toString()
		{
			LinkedListNode node = head.next;
			StringBuilder buf = new StringBuilder();
			while (node != head)
			{
				buf.append(node.toString()).append(", ");
				node = node.next;
			}
			return buf.toString();
		}
	}

	/**
	 * Doubly linked node in a LinkedList. Most LinkedList implementations
	 * keep the equivalent of this class private. We make it public so
	 * that references to each node in the list can be maintained
	 * externally.
	 * 
	 * Exposing this class lets us make remove operations very fast.
	 * Remove is built into this class and only requires two reference
	 * reassignments. If remove existed in the main LinkedList class, a
	 * linear scan would have to be performed to find the correct node to
	 * delete.
	 * 
	 * The linked list implementation was specifically written for the
	 * Jive cache system. While it can be used as a general purpose linked
	 * list, for most applications, it is more suitable to use the linked
	 * list that is part of the Java Collections package.
	 */
	private static class LinkedListNode
	{

		public LinkedListNode previous;

		public LinkedListNode next;

		public Object object;

		/**
		 * This class is further customized for the Jive cache
		 * system. It maintains a timestamp of when a Cacheable
		 * object was first added to cache. Timestamps are stored as
		 * long values and represent the number of milliseconds
		 * passed since January 1, 1970 00:00:00.000 GMT.
		 * <p>
		 * 
		 * The creation timestamp is used in the case that the cache
		 * has a maximum lifetime set. In that case, when [current
		 * time] - [creation time] > [max lifetime], the object will
		 * be deleted from cache.
		 */
		public long timestamp;

		/**
		 * Constructs a new linked list node.
		 * 
		 * @param object
		 *                  the Object that the node represents.
		 * @param next
		 *                  a reference to the next LinkedListNode
		 *                  in the list.
		 * @param previous
		 *                  a reference to the previous
		 *                  LinkedListNode in the list.
		 */
		public LinkedListNode(Object object, LinkedListNode next, LinkedListNode previous)
		{
			this.object = object;
			this.next = next;
			this.previous = previous;
		}

		/**
		 * Removes this node from the linked list that it is a part
		 * of.
		 */
		public void remove()
		{
			previous.next = next;
			next.previous = previous;
		}

		/**
		 * Returns a String representation of the linked list node
		 * by calling the toString method of the node's object.
		 * 
		 * @return a String representation of the LinkedListNode.
		 */
		public String toString()
		{
			return object.toString();
		}
	}
}